The present invention relates to a back-pressure type ATM (Asynchronous Transfer Mode) switch, and particularly to an economical and flexible configuration of the back-pressure type ATM switch for guaranteeing fair throughput making use of an internal rate control.
In conventional back-pressure type ATM switches such as those disclosed in a Japanese patent application entitled xe2x80x9cA Method of Priority Control in an Output-buffer Type ATM Switchxe2x80x9d and laid open as a Provisional Publication No. 297840/""95, or a Japanese patent application entitled xe2x80x9cA Back-pressure Type ATM Switchxe2x80x9d and laid open as a Provisional Publication No. 223173/""96, cells toward a congestion node are suspended to be read out from input buffers according to a xe2x80x9cback-pressurexe2x80x9d signals which are generated at the congestion node in the ATM switch to be fed-back to the input buffers.
FIG. 7 is a block diagram schematically illustrating an example of the back-pressure control applied in a conventional I/O (In/Out) buffer type ATM switch.
In the example of FIG. 7, there are comprised m input buffers 71-1 to 71-m each corresponding to each of m input ports, n output buffers 72-1 to 72-n each corresponding to each of n output ports, and a switch 73 for switching each of cells read out from the input buffers 71-1 to 71-m into one of output buffers 72-1 to 72-n according to header information of the cell (m and n being positive integers).
In each of the input buffers 71-1 to 71-m, sxc3x97n input queues (s being an positive integer) are prepared each corresponding to each of s QoS (Quality of Service) classes of cells to be switched to each of the n output buffers 72-1 to 72-n, while s output queues are prepared each corresponding to each of s QoS classes in each of the output buffers 72-2 to 72-m.
From each of the output buffers 72-1 to 72-n, s back-pressures are generated to be fed-back to every of the input buffers 71-1 to 71-m. Each of the sxc3x97n back-pressures suspends read-out of cells from corresponding each of sxc3x97n input queues of every of the input buffers 71-1 to 71-m, when it is enabled.
Thus, a back-pressure control is realized in the ATM switch of FIG. 7 for obtaining high robustness against instantaneous excessive traffic.
However, according to above back-pressure control, there arise unfair throughputs among the input ports. Consider, for example, only one connection of a certain QoS class toward a certain output port is established in a first input port, while ten connections of the same QoS class toward the same output port are established in a second input port. Then, throughput given for each connection of the second input port becomes {fraction (1/10)} of that of the first input port, when read-out of cells from concerning two input queues are controlled in the same way, resulting in unfair bandwidth allocation for connections requiring the same QoS among different input ports.
For dealing with this unfair bandwidth allocation, an xe2x80x9cinternal rate controlxe2x80x9d is proposed by Shinohara, et al., in xe2x80x9cLarge Scale ATM Switch with Multiple QoS Guaranteexe2x80x9d, pp. 73 to 78, TECHNICAL REPORT OF IEICE, SSE96-55 (1996-08), and in xe2x80x9cInternal Congestion Contrl in Large Scale ATM Switchxe2x80x9d, pp. 13 to 18, TECHNICAL REPORT OF IEICE, SSE96-131, CQ96-41 (1996-12). In the internal rate control, an open-loop control is applied to bandwidth guaranteed QoS classes like CBR (Constant Bit Rate) and VBR (Variable Bit Rate) wherein a bandwidth is allocated for each connection, and a closed-loop control according to internal congestion is applied to no bandwidth guaranteed QoS classes like ABR (Available Bit Rate) and UBR (Unspecified Bit Rate).
FIG. 8 is a block diagram schematically illustrating the above closed-loop control applied to the no bandwidth guaranteed QoS classes in a conventional I/O buffer type ATM switch.
For performing the internal rate control, a rate shaper S having a virtual queue (virtual and not depicted in the drawing) is provided for each of nxc3x97s input queues, corresponding to each of n output ports and s QoS classes, in each of m input buffers 81-1 to 81-m. In the internal rate control, the rate shaper S virtually reads out cells from its input queue at a rate, or a read-out speed, calculated according to rate information delivered from a rate calculator 84, and the cells read out by the rate shaper S are virtually transferred in the virtual queue to be read out by the read controller when corresponding back-pressure is not enabled.
The rate information is calculated for each of nxc3x97s output queues, that is, for each of s QoS class toward each of n output ports, according to queue length of a concerning output queue (hatched output queue 821 of FIG. 8, for example), global queue length, namely, total queue length of every virtual queue (in hatched rate shapers accompanying input queues 811-1 to 811-m, in the example) corresponding to the concerning output queue (821) and cells on a switch 83 toward the concerning output queue (821), and a total number of connections, that is, a sum of active VCs (Virtual Channels) assigned to every input queue (811-1 to 811-m) corresponding to the concerning output queue (821). The read controllers are controlled by back-pressures generated by the switch 83
The rate information defines a read-out speed per a VC, and the rate shaper S shifts cells from the output queue to the virtual queue at a speed calculated by (rate information)xc3x97(number of active VCs of the input queue). From every of the virtual queues not suspended by corresponding back-pressure, cells are read out according to rotation priority read-out control (reading out cells from queues in turn).
Thus, fair bandwidth allocation according to closed-loop control is realized for no bandwidth guaranteed QoS classes like ABR and UBR, in the I/O buffer type ATM switch of FIG. 8.
As to bandwidth guaranteed QoS classes like CBR and VBR, an open-loop control, that is, a fixed rate cell-transfer in proportion to the guaranteed bandwidth is performed according to fixed priority read-out control (reading out cells from queues in order of priority).
However, in the above prior art, the fixed rate cell-transfer and the fixed priority read-out control is required for queues assigned to bandwidth guaranteed QoS classes to be open-loop-controlled, while the variable speed rate shaper and the rotation priority read-out control is needed for queues assigned to no bandwidth guaranteed QoS classes to be closed-loop-controlled.
Therefore, for enabling to assign a queue flexibly to any of the bandwidth guaranteed QoS classes and the no bandwidth guaranteed QoS classes, the queue should be prepared with every one of the fixed rate cell-transfer, variable speed rate shaper, fixed priority read-out control and the rotation priority read-out control, which requires large and complicated hardware. In other words, number of QoS classes of the open-loop control and the closed-loop control are both fixed because of hardware restriction, in the above prior art.
Furthermore, a fixed buffer space must be allocated for each of the bandwidth guaranteed QoS classes, and for performing the closed-loop control effectively, certain amount of buffer space must be also allocated for each of no bandwidth guaranteed QoS classes, otherwise the cell rejection rate increases and the acceptable connection number is restricted. Therefore, the number of QoS classes are fixed, efficiency of buffer space is inevitably lowered.
Therefore, a primary object of the present invention is to provide a back-pressure type ATM switch wherein desired QoS class setting is realized by enabling to assign any queue to any QoS class without needing large hardware. Another object of the invention is to increase the acceptable connection number and decrease the cell rejection rate by improving efficiency of buffer space making use of a common memory.
In order to achieve the object, in a back-pressure type ATM switch of the invention, for switching cells supplied from at least one input port into at least one output port, having input buffers each corresponding to each of said at least one input port and comprising a plurality of input queues, an input queue write controller for performing write control of the cells into the input queues and an input queue read controller for performing read control of the cells buffered in the input queues according to back-pressures, output buffers each corresponding to each of said at least one output port and comprising a plurality of output queues, an output queue write controller for performing write control of the cells into the output queues and generating the back-pressures and an output queue read controller for performing read control of the cells buffered in the output queues, and a switch for switching the cells read out from the input buffers into the output buffers according to header information of the cells; each of the input buffers further comprises:
a resource manager for performing rejection control of the input queue write controller according to minimum guaranteed resources and rejection threshold queue length defined for each of the input queues, each of QoS-class virtual resources, and a common resource;
each of the minimum guaranteed resources indicating a buffer space to be used exclusively by each of the input queues;
the rejection threshold queue length defined for each of the input queues indicating maximum allowable queue length of each of the input queues;
the rejection threshold queue length defined for each of QoS-class virtual resources indicating maximum allowable queue length of each of QoS-class virtual resources, each of the QoS-class virtual resources representing a sum of certain of the input queues which are assigned to each of QoS classes defining service levels of the back-pressure type ATM switch; and
the rejection threshold queue length defined for the common resource indicating a buffer space to be used commonly by each of the input queues.
In the back-pressure type ATM switch;
the rejection threshold queue length defined for the common resource is given by reducing all of the minimum guaranteed resources from a total buffer space allocated to said each of the input buffers;
any of the cells is rejected when queue length of one of the input queues wherein said any is to be buffered is not shorter than the rejection threshold queue length defined to said one;
any of the cells is rejected when queue length of one of the QoS-class virtual resources wherein said any is to be sorted is not shorter than the rejection threshold queue length defined to said one of the QoS-class virtual resources; and
any of the cells is rejected when queue length of the common resource is not shorter than the rejection threshold queue length defined to the common resource, and queue length of one of the input queues wherein said any is to be buffered is not shorter than corresponding one of the minimum guaranteed resources.
Therefore, a dynamic and efficient memory allocation is enabled in the invention together with flexible setting of rejection service levels.
The back-pressure type ATM switch further comprises:
shapers each accompanying to each of the input queues of each of the input buffers for shifting cells from said each of the input queues to a virtual queue from where the cells are read out by the input queue read controller at a speed obtained by adding a minimum guaranteed speed to a product of rate information designated to said each of the input queues and a number of active VCs assigned to said each of the input queues; and
a rate controller for calculating the rate information to be designated for each of the input queues of every of the input buffers according to a function of a sum of queue length of the virtual queue of said each of the input queues of every of the input buffers and a sum of a number of active VCs assigned to said each of the input queues of every of the input buffers.
Therefore, setting of a desired variety of bandwidth service levels is enabled with the same queue configuration throughout from the bandwidth guaranteed QoS classes like CBR/VBR to the no bandwidth guaranteed QoS classes like ABR/UBR.
Still further, each of the input buffers of the back-pressure type ATM switch comprises a back-pressure connector provided to the input queue read controller for defining correspondence between second back-pressures to be referred to by the input queue read controller and the back-pressures generated by the output queue write controller of every of the output buffers.
Therefore, setting of a desired delay priority order is enabled independent of the bandwidth service level with no restriction between numbers of QoS classes in the input buffer and the output buffer.
Thus, a variety of high-quality and flexible services can be served with high hardware/software efficiency, according to the invention.